class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """

        def search(start, end):
            left_index = start
            right_index = start
            state = 0
            out = ''
            while right_index < end:
                if state == 0:
                    if ord('0') <= ord(s[right_index]) <= ord('9'):
                        left_index = right_index
                        state = 1
                        right_index += 1
                    else:
                        out += s[right_index]
                        right_index += 1
                else:
                    if state == 1:
                        if ord('0') <= ord(s[right_index]) <= ord('9'):
                            right_index += 1
                        else:
                            base = int(s[left_index: right_index])
                            state = 2
                            right_index += 1
                            left_index = right_index
                            count = 1
                    else:

                        if s[right_index] == '[':
                            count += 1
                        else:
                            if s[right_index] == ']':
                                count -= 1
                        if count == 0:
                            state = 0
                            out += (base * search(left_index, right_index))
                        right_index += 1
            return out
        out = search(0, len(s))
        return out


data = Solution()
s = "30[a20[c]]"
print(data.decodeString(s))
s = "3[a]2[bc]"
print(data.decodeString(s))
s = "2[abc]3[cd]ef"
print(data.decodeString(s))
s = "abc3[cd]xyz"
print(data.decodeString(s))
